import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SolutionInterview8_12 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans=new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        int[] f=new int[n];
        Map<Integer,Integer> map1=new HashMap<>();
        Map<Integer,Integer> map2=new HashMap<>();
        dfs(0,n,f,map1,map2,temp,ans);
        return ans;
    }

    private void dfs(int k, int n, int[] f, Map<Integer, Integer> map1, Map<Integer, Integer> map2, List<Integer> temp, List<List<String>> ans) {
        if (k==n){
            ans.add(deal(temp));
            return;
        }
        for (int i=0;i<n;i++){
            if (f[i]==0 && map1.getOrDefault(k+i,0)==0 && map2.getOrDefault(k-i,0)==0){
                f[i]=1;
                map1.put(k+i,1);
                map2.put(k-i,1);
                temp.add(i);
                dfs(k+1,n,f,map1,map2,temp,ans);
                temp.remove(temp.size()-1);
                map1.put(k+i,0);
                map2.put(k-i,0);
                f[i]=0;
            }
        }
    }

    private List<String> deal(List<Integer> temp) {
        List<String> ans=new ArrayList<>();
        for (int i=0;i<temp.size();i++){
            StringBuilder stringBuilder=new StringBuilder();
            for (int j=0;j<temp.size();j++){
                if (j==temp.get(i)){
                    stringBuilder.append('Q');
                }else {
                    stringBuilder.append('.');
                }
            }
            ans.add(stringBuilder.toString());
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview8_12().solveNQueens(4));
    }
}
